/*
 * covertree.h
 *
 *  Created on: Jun 1, 2011
 *      Author: tqlong
 */

#ifndef COVERTREE_H_
#define COVERTREE_H_

#include <vector>

template<typename Data>
  class CoverTree
  {
  public:
    typedef Data dataset_type;
    typedef typename Data::vec_type vec_type;
  public:
    CoverTree(dataset_type& data);

    CoverTree(CoverTree* parent, int start, int end, double level, bool isSelf);

    ~CoverTree();

    inline int n() const { return end_ - start_; }

    inline int n_child() const { return children_.size(); }

    inline int origIdx(int i) const { return idx_[start_ + i]; }

    inline const vec_type& get(int i) const { return data_.get(origIdx(i)); }

    inline CoverTree* child(int i) const { return children_[i]; }

    inline void addChild(CoverTree* c) { children_.push_back(c); }

    inline CoverTree* parent() const { return parent_; }

    void buildTree();

    void split();

    void save(std::ostream& f);
    void save(const std::string& fName);

    void load(std::istream& f);
    void load(const std::string& fName);

    void dump(int level = 0);
  protected:
    typedef std::vector<int> vint_type;
    typedef std::vector<CoverTree*> vtree_type;

    dataset_type &data_;
    vint_type &idx_;
    CoverTree* parent_;
    vtree_type children_;
    int start_, end_;
    double level_;
    bool isSelfChild_;

    void swap(int i, int j)
    {
      int temp = idx_[start_ + i];
      idx_[start_ + i] = idx_[start_ + j];
      idx_[start_ + j] = temp;
    }

    double distance(int i, int j)
    {
      return arma::norm(get(i)-get(j), 2); // l2 norm, TODO other norms
    }
  };

#include "covertree_impl.h"

#endif /* COVERTREE_H_ */
